#include<bits/stdc++.h>
using namespace std;
int plen,ptop,pstk[40];
char rdc[1<<20],out[1<<20],*rS,*rT;
#define gc() (rS==rT?rT=(rS=rdc)+fread(rdc,1,1<<20,stdin),(rS==rT?EOF:*rS++):*rS++)
#define pc(x) out[plen++]=(x)
#define flush() fwrite(out,1,plen,stdout),plen=0
template<class T=int>inline T read(){
    T x=0;char ch;bool f=1;
    while(!isdigit(ch=gc()))if(ch=='-')f^=1;
    do x=(x<<1)+(x<<3)+(ch^48);while(isdigit(ch=gc()));
    return f?x:-x;
}
template<class T=int>inline void write(T x){
	if(plen>=1000000)flush();
	if(!x)return pc('0'),void();
	if(x<0)pc('-'),x=-x;
	for(;x;x/=10)pstk[++ptop]=x%10;
	while(ptop)pc(pstk[ptop--]+'0');
}
inline void write(const char*s){
	if(plen>=1000000)flush();
	for(int i=0;(*(s+i))!='\000';pc(*(s+(i++))));
}
inline void write(char*const s){
	if(plen>=1000000)flush();
	for(int i=0;(*(s+i))!='\000';pc(*(s+(i++))));
}
const int Maxn=5e5+5,inf=1e9+7;
int n,m,q;
int fa[Maxn];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
namespace sub1{
	int las[Maxn];
	inline void sol(int L,int R){
		int ans=R-L+1;
		set<int>s;
		for(int i=L;i<=R;i++)las[find(i)]=0;
		for(int i=L;i<=R;i++){
			if(las[find(i)])s.erase(las[find(i)]);
			las[find(i)]=i-inf,s.insert(i-inf);
		}
		
		for(int i=L;i<=R;i++){
			s.erase(las[find(i)]);
			las[find(i)]=i;
			s.insert(i);
			ans=min(ans,i-(*s.begin())+1);
		}write(ans);pc('\n');
	}
	inline void solve(){
		while(q--){
			int L=read(),R=read();
			sol(L,R);
		}
		flush();
	}
}
namespace sub2{
	struct Tree{
		int val,tag,tag1;
	}t[Maxn<<2];
	void build(int x,int l,int r){
		t[x]={inf,inf,0};if(l==r)return;
		int mid=l+r>>1;
		build(x<<1,l,mid);build(x<<1|1,mid+1,r);
	}
	inline void add_(int x,int p){
		t[x].val=min(t[x].val,p);
		t[x].tag=min(t[x].tag,p);
	}
	inline void del_(int x){
		t[x].val=t[x].tag=inf;
		t[x].tag1=1;
	}
	inline void spread(int x){
		if(t[x].tag1){
			del_(x<<1);del_(x<<1|1);
			t[x].tag1=0;
		}
		if(t[x].tag<inf){
			add_(x<<1,t[x].tag);add_(x<<1|1,t[x].tag);
			t[x].tag=inf;
		}
	}
	void change(int x,int l,int r,int L,int R,int p){
		if(L>R)return;
		if(L<=l&&r<=R)return void(add_(x,p));
		int mid=l+r>>1;spread(x);
		if(mid>=L)change(x<<1,l,mid,L,R,p);
		if(mid<R)change(x<<1|1,mid+1,r,L,R,p);
		t[x].val=min(t[x<<1].val,t[x<<1|1].val);
	}
	void modify(int x,int l,int r,int L,int R){
		if(L>R)return;
		if(L<=l&&r<=R)return void(del_(x));
		int mid=l+r>>1;spread(x);
		if(mid>=L)modify(x<<1,l,mid,L,R);
		if(mid<R)modify(x<<1|1,mid+1,r,L,R);
		t[x].val=min(t[x<<1].val,t[x<<1|1].val);
	}
	int query(int x,int l,int r,int d){
		if(l==r)return t[x].val;
		int mid=l+r>>1;spread(x);
		if(mid>=d)return query(x<<1,l,mid,d);
		return query(x<<1|1,mid+1,r,d);
	}
	int las[Maxn];
	struct Query{
		int l,id;
	};
	vector<Query>Q[Maxn];
	int ans[Maxn];
	inline void solve(){
		for(int i=1;i<=q;i++){
			int l=read(),r=read();
			Q[r].push_back({l,i});
		}
		
		build(1,1,n);
		set<int>s;s.insert(-inf);
		for(int i=1;i<=n;i++)if(find(i)==i)las[i]=i-inf,s.insert(i-inf);
		
	//	for(int i=1;i<=n;i++)printf("find(%d)=%d\n",i,find(i));
		
		for(int i=1;i<=n;i++){
			auto IT=prev(s.lower_bound(las[find(i)]));
			int LL=max(0,(*IT))+1;
			
			s.erase(las[find(i)]);
			s.insert(i);
			
	//		printf("%d:\n",i);
	//		for(auto It=s.begin();It!=s.end();It++)printf("%d ",*It);
	//		puts("");
			
			int tp=i-(*s.upper_bound(las[find(i)]))+1;
			change(1,1,n,LL,las[find(i)],tp);
			int pre=max(0,las[find(i)])+1;
	//		printf("fewoifhewoih %d:%d\n",i,pre);
			modify(1,1,n,pre,i);
			for(auto it=s.upper_bound(pre-1);it!=s.end();it++){
				change(1,1,n,pre,(*it),i-(*it)+1);
				pre=max(0,(*it))+1;
			}
			
			las[find(i)]=i;
			for(Query it:Q[i]){
				ans[it.id]=query(1,1,n,it.l);
			}
		}
		for(int i=1;i<=q;i++)write(ans[i]),pc('\n');
		flush();
	}
}

int main(){
	freopen("destory.in","r",stdin);
	freopen("destory.out","w",stdout);
	n=read();m=read();q=read();
	for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=1;i<=m;i++){
		int u=read(),v=read();
		fa[find(u)]=find(v);
	}
	if(1ll*n*q<=1e6)sub1::solve(),exit(0);
	
	int tot=0;for(int i=1;i<=n;i++)tot+=(find(i)==i);
	if(tot==1){
		while(q--){
			int L=read(),R=read();
			write(1);pc('\n');
		}flush();
		return 0;
	}
	sub2::solve(),exit(0);
	return 0;
}
/*
5 2 5
2 2
4 1
1 1
1 1
2 5
4 5
3 5
*/
